package chapter01;

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {
    //回溯 DFS
    private List<String> stringList=new ArrayList<>();
    private int couple=0;
    private StringBuilder builder=new StringBuilder();

    public List<String> generateParenthesis(int n) {
        couple=n;
        back(builder,0,0);
        return stringList;
    }

    public void back(StringBuilder stringBuilder,int leftCount,int rightCount){
        if(stringBuilder.toString().length()==couple*2){
            stringList.add(stringBuilder.toString());
            return;
        }
        if(leftCount<couple){
            back(stringBuilder.append('('),leftCount+1,rightCount);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
        if(rightCount<leftCount){
            back(stringBuilder.append(')'),leftCount,rightCount+1);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
    }
}
